package array

func search(nums []int, target int) int {

	if len(nums) == 0 {
		return -1
	}

	left, right := 0, len(nums)-1

	for left < right {

		mid := (left + right) / 2

		if nums[mid] == target {
			return mid
		}

		if nums[mid] >= nums[0] {
			if nums[0] < target && target < nums[mid] {
				right = mid - 1
			} else {
				left = mid + 1
			}
		} else {
			if nums[mid] < target && target < nums[right] {
				left = mid + 1
			} else {
				right = mid - 1
			}
		}
	}

	if nums[left] == target {
		return left
	}

	return -1

}
